package Leetcode第二期;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : K k
 * @date : 15:34 2020/10/18
 * 现在你总共有 n 门课需要选，记为 0 到 n-1。
 *
 * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
 *
 * 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
 *
 * 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
 *
 * 示例 1:
 *
 * 输入: 2, [[1,0]]
 * 输出: [0,1]
 * 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 * 示例 2:
 *
 * 输入: 4, [[1,0],[2,0],[3,1],[3,2]]
 * 输出: [0,1,2,3] or [0,2,1,3]
 * 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
 *      因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
 */
public class 课程表II_210 {
    //DFS效率高于BFS

    //思路：BFS 判断有向图是否存在环 存在则false
    List<List<Integer>> edges;
    int[] indeg;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        int[] result=new int[numCourses];
        int index=0;
        //计算每个结点的入度
        indeg = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]); //记录可以学的课程 用于用入栈可以直接找到可修课程
            ++indeg[info[0]]; //记录该课程对应的前置课程
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) {
                //入度为0的入栈
                queue.offer(i);
            }
        }
        int visited = 0;
        while (!queue.isEmpty()) {
            ++visited; //统计访问过的结点数
            int u = queue.poll();
            for (int v : edges.get(u)) {
                //获取能学的课程 并消入边，减少该结点的入度
                --indeg[v];
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
            if(index>=numCourses){
                continue;
            }else {
                result[index++]=u;
            }
        }
        //若无环，则访问数为总数
        if(visited == numCourses){
            return result;
        }else{
            return new int[0];
        }
    }

    //方法1：DFS DFS是从后往前
    int[] visit;
    boolean valid = true; //有无环的标志，若出现环则为false，直接退出
    int[] result;
    int index;

    public int[] findOrderA(int numCourses, int[][] prerequisites) {
        this.edges = new ArrayList<List<Integer>>();
        this.visit = new int[numCourses];
        //结果集的下标
        this.index=numCourses-1;
        this.result=new int[numCourses];
        //构造有向序列列表
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        //初始化
        for (int[] info : prerequisites) {
            //有向对
            edges.get(info[1]).add(info[0]);
        }

        for (int i = 0; i < numCourses && valid; i++) {
            //dfs 访问所需课程
            if (visit[i] == 0) {
                dfsSolver(i);
            }
        }
        if (!valid){
            return new int[0];
        }
        return result;
    }

    //对每一个课程进行查找，查找的是它的前置课程，若前置课程已被访问则出现了环
    private void dfsSolver(int u) {
        visit[u] = 1;
        for (int v : edges.get(u)) {
            //剪枝
            if (visit[v] == 0) {
                dfsSolver(v);
                if (!valid) {
                    return;
                }
            } else if (visit[v] == 1) {
                valid = false;
                return;
            }
        }
        //剪枝
        //表明该课程已经搜索过 可以直接填入结果集，从后往前填
        visit[u] = 2;
        result[index--]=u;
    }
}
